Grokking Oracle Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Oracle Easy
Count Number of Pairs With Absolute Difference K (easy)
Solution: Count Number of Pairs With Absolute Difference K
Degree of an Array (easy)
Solution: Degree of an Array
Find Subsequence of Length K With the Largest Sum (easy)
Solution: Find Subsequence of Length K With the Largest Sum
Rectangle Overlap (easy)
Solution: Rectangle Overlap
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Island Perimeter (easy)
Solution: Island Perimeter
Climbing Stairs (easy)
Solution: Climbing Stairs
Move Zeroes (easy)
Solution: Move Zeroes
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Valid Parentheses (Easy)
Solution: Valid Parentheses
Oracle Medium
Longest Palindromic Substring (medium)
Solution: Longest Palindromic Substring
Single Element in a Sorted Array (medium)
Solution: Single Element in a Sorted Array
Pairs of Songs With Total Durations Divisible by 60 (medium)
Solution: Pairs of Songs With Total Durations Divisible by 60
Search a 2D Matrix II (medium)
Solution: Search a 2D Matrix II
Minimize Maximum of Array (medium)
Solution: Minimize Maximum of Array
Asteroid Collision (medium)
Solution: Asteroid Collision
Combination Sum (medium)
Solution: Combination Sum
Binary Tree Right Side View (medium)
Solution: Binary Tree Right Side View
Sort Colors (medium)
Solution: Sort Colors
Group Anagrams (Medium)
Solution: Group Anagrams
Decode String (Medium)
Solution: Decode String
Number of Islands (medium)
Solution: Number of Islands
Binary Tree Zigzag Level Order Traversal (medium)
Solution: Binary Tree Zigzag Level Order Traversal
Longest Common Subsequence (medium)
Solution: Longest Common Subsequence
Rotting Oranges (medium)
Solution: Rotting Oranges
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Spiral Matrix (medium)
Solution: Spiral Matrix
Container With Most Water (Medium)
Solution: Container With Most Water
3Sum (medium)
Solution: 3Sum
Simplify Path (medium)
Solution: Simplify Path
Next Permutation (medium)
Solution: Next Permutation
Basic Calculator II (medium)
Solution: Basic Calculator II
Merge Intervals (medium)
Solution: Merge Intervals
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Longest Increasing Subsequence (medium)
Solution: Longest Increasing Subsequence
Validate Binary Search Tree (medium)
Solution: Validate Binary Search Tree
Integer to English Words (hard)
Solution: Integer to English Words
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Merge K Sorted Lists (hard)
Solution: Merge K Sorted Lists
Max Points on a Line (hard)
Solution: Max Points on a Line
Sudoku Solver (hard)
Solution: Sudoku Solver
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Constrained Subsequence Sum (hard)
Solution: Constrained Subsequence Sum
Solution: Basic Calculator II

Problem Statement

Given a string s, representing the mathematical expression, evaluate the expression and return the integer value.

The integer division should truncate toward zero.

*Note: You are not allowed to use the built-in functions like eval().

Examples

Example 1:

  • Input: "8*5/4+3-2"
  • Expected Output: 11
  • Justification: The calculation proceeds as follows: 8*5 = 40, 40/4 = 10, 10+3 = 13, 13-2 = 11.

Example 2:

  • Input: "10+20/5*3"
  • Expected Output: 22
  • Justification: The order of operations gives 20/5 = 4, 4*3 = 12, and 10+12 = 22.

Example 3:

  • Input: "50-25+5*3/2*2-10/2"
  • Expected Output: 34
  • Justification: Following the order of operations: 50 - 25 = 25, (15/2) = 7 (rounded down), 7*2 = 14, 25+14 = 39, 10/2 = 5, and 39 - 5 = 34.

Solution

To solve this problem, our approach blends linear parsing with immediate evaluation of arithmetic operations. This methodology effectively addresses the challenge of respecting the standard order of operations (multiplication and division prior to addition and subtraction) within a single pass through the expression. The logic behind this approach is to evaluate and accumulate partial results as soon as possible, especially when dealing with multiplication and division, which have higher precedence.

The efficiency of this method lies in its ability to process the expression in a single sweep, thereby minimizing the need for backtracking or re-evaluating portions of the expression. By updating the cumulative result and the last evaluated number at each step, based on the current operation, the algorithm ensures that the most recent operation is always applied correctly. This real-time processing approach not only maintains the correct order of operations but also streamlines the computational process, leading to a solution that is both time and space-efficient.

Step-by-Step Algorithm

  1. Initialize currentNumber, lastNumber, and result to 0, and set operation to '+'.
  2. Iterate over each character in the input string:
    • If the character is a digit, update currentNumber accordingly.
    • If the character is a non-digit, non-space, or it's the end of the string:
      • If operation is '+' or '-', add lastNumber to result. Update lastNumber to currentNumber or -currentNumber based on operation.
      • If operation is '*', multiply lastNumber with currentNumber.
      • If operation is '/', divide lastNumber by currentNumber.
      • Update operation to the current character.
      • Reset currentNumber to 0.
  3. After the loop, add lastNumber to result for the final total.

Algorithm Walkthrough

let's consider input: "50-25+5*3/2*2-10/2"

Certainly, let's correct the walkthrough of the code with the input "50-25+5*3/2*2-10/2". We'll carefully trace through the arithmetic and ensure accurate computation at each step.

  1. Initialization:

    • currentNumber = 0, lastNumber = 0, result = 0, operation = '+'.
  2. Processing each character:

    • Iterate through each character of the string.
  3. First Character '5':

    • currentNumber becomes 5.
  4. Second Character '0':

    • currentNumber becomes 50.
  5. Third Character '-':

    • Operation is +, so lastNumber = 50 (as currentNumber is 50).
    • result becomes 0 (0 + 0).
    • operation updated to '-'.
    • currentNumber reset to 0.
  6. Next Characters '25':

    • currentNumber becomes 25.
  7. Character '+':

    • Operation is '-', so lastNumber = -25.
    • result becomes 50 (0 + 50).
    • operation updated to '+'.
    • currentNumber reset to 0.
  8. Next Characters '5':

    • currentNumber becomes 5.
  9. Character '*':

    • Operation is '+', result becomes 25 (50 - 25).
    • Update `lastNumber = 5
    • operation updated to '*'.
    • currentNumber reset to 0.
  10. Next Characters '3':

    • currentNumber becomes 3.
  11. Character '/':

    • Operation is '*', so lastNumber becomes 15 (5 * 3).
    • operation updated to '/'.
    • currentNumber reset to 0.
  12. Next Characters '2':

    • currentNumber becomes 2.
  13. Character '*':

    • Operation is '/', so lastNumber becomes 7 (15 / 2, rounded down for integer division).
    • operation updated to '*'.
    • currentNumber reset to 0.
  14. Next Characters '2':

    • currentNumber becomes 2.
  15. Character '-':

    • Operation is '*', so lastNumber becomes 14 (7 * 2).
    • result becomes 39 (25 + 14).
    • operation updated to '-'.
    • currentNumber reset to 0.
  16. Next Characters '10':

    • currentNumber becomes 10.
  17. Character '/':

    • Operation is '-', so lastNumber becomes -10.
    • result remains 39.
    • operation updated to '/'.
    • currentNumber reset to 0.
  18. Next Characters '2':

    • currentNumber becomes 2.
  19. End of String:

    • Operation is '/', so lastNumber becomes -5 (10 / 2, integer division).
    • result becomes 34 (39 - 5).
  20. Final Calculation:

    • result is 34.

Code

Java

. . . .

Complexity Analysis

  • Time Complexity: The algorithm has a linear time complexity of O(N), where N represents the length of the input string. This is because the algorithm processes each character in the string exactly once.

  • Space Complexity: The space complexity of the algorithm is O(1), or constant space complexity. This is due to the use of a fixed number of variables regardless of the size of the input string.

Basic Calculator II (medium)
Merge Intervals (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis